package com.algorithms.sorts.advances;

import com.algorithms.sorts.Sort;

/**
 * HeapSort<br>
 * Complexity O(N*logN)<br><br>
 * 
 * algorithms:<br>
 * 
 * @author minhld
 *
 */
public class HeapSort extends Sort{
	
	int tempLength = 0;
	
	public HeapSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "HeapSort";
	}
	
	@Override
	public int[] sort(){
		int lastParent = (this.length - 1) / 2;
		// make the heap
		for (int i = lastParent; i >= 0; i--){
			trickleDown(i);
		}
		
		for (int i = 0; i < this.length; i++){
			data[this.length - i - 1] = remove(this.length - i);
		}
		
		return this.data;
	}
	
	private int remove(int len){
		// swap the root item with the rightmost item
		int deletedItem = data[0];
		data[0] = data[len - 1];
		
		// trickle down the root item
		trickleDown(0, len - 1);
		
		return deletedItem;
	}	
	
	private void trickleDown(int index){
		// current index
		int cIdx = index;
		int root = data[index];

		//left child index and right child index
		int lChIdx, rChIdx;

		while (cIdx <= (this.length - 1) / 2){
			
			// get left & right children indexes 
			lChIdx = cIdx * 2 + 1;
			rChIdx = lChIdx + 1;
			
			this.numOfProcess++;

			// when left & right children are not available
			if (lChIdx > this.length - 1){
				break;
			}

			// when only left child node available
			if (this.length - 1 == lChIdx){
				if (root < data[lChIdx]){
					// swap if current node has key smaller than 
					// its left child node
					data[cIdx] = data[lChIdx];
					
					// moves to the left node
					cIdx = lChIdx;
					
					this.numOfCopy++;					
				}
				
				break;
			}
			
			// when both children are available
			// if current node should be swapped with the left child
			if (root < data[lChIdx] && data[lChIdx] >= data[rChIdx]){
				data[cIdx] = data[lChIdx];

				this.numOfCopy++;
				
				// moves download to the left child 
				cIdx = lChIdx;
				continue;
			}
			
			// if current node should be swapped with the right child
			if (root < data[rChIdx] && data[lChIdx] <= data[rChIdx]){
				data[cIdx] = data[rChIdx];
				
				this.numOfCopy++;
				
				// moves to the right child index
				cIdx = rChIdx;
				continue;
			}
			
			// no more moves
			break;
		}
		
		// swap the root with the current index
		data[cIdx] = root;
		
		this.numOfCopy++;
	}
	
	private void trickleDown(int index, int len){
		// current index
		int cIdx = index;
		int root = data[index];

		//left child index and right child index
		int lChIdx, rChIdx;

		while (cIdx <= (len - 1) / 2){
			
			// get left & right children indexes 
			lChIdx = cIdx * 2 + 1;
			rChIdx = lChIdx + 1;
			
			this.numOfProcess++;
			
			// when left & right children are not available
			if (lChIdx > len - 1){
				break;
			}
			
			// when only left child node available
			if (len - 1 == lChIdx){
				if (root < data[lChIdx]){
					// swap if current node has key smaller than 
					// its left child node
					data[cIdx] = data[lChIdx];
					
					cIdx = lChIdx;
					this.numOfCopy++;
					
				}
				
				break;
			}
			
			// when both children are available
			// if current node should be swapped with the left child
			if (root < data[lChIdx] && data[lChIdx] >= data[rChIdx]){
				data[cIdx] = data[lChIdx];

				this.numOfCopy++;
				
				// moves down to the left child 
				cIdx = lChIdx;
				continue;
			}
			
			// if current node should be swapped with the right child
			if (root < data[rChIdx] && data[lChIdx] <= data[rChIdx]){
				data[cIdx] = data[rChIdx];
				
				this.numOfCopy++;
				
				// moves to the right child index
				cIdx = rChIdx;
				continue;
			}
			
			// no more moves
			break;
		}
		
		// swap the root with the current index
		data[cIdx] = root;
		
		this.numOfCopy++;
	}
}
